package LearnAlgorithm.d_标准查找算法and标准排序算法;

public class c1字符串匹配RabinKarp {
	private static final long seed = 31;
	
	public static void main(String[] args) {
		String string = "ABAxBxABAxBxABAxBxABA";
		String keys = "ABA";
		long before = System.currentTimeMillis();
		rabinKrapMatch(string, keys);
		util.Util.duration(before);
	}
	
	/**
	 * O(M*N)
	 * 默认哈希的RabinKarp
	 * @param mother
	 * @param child
	 */
	public static void rabinKrapMatch(String mother, String child) {
		long childHashValue = hash(child);
		int length = child.length();
		for (int i = 0; i + length <= mother.length(); i++) {
			long motherPartHashValue = hash(mother.substring(i, i + length));
			if (motherPartHashValue == childHashValue) {
				System.out.println("match begin:" + i + ", match end:" + (i + length - 1));
			}
		}
	}
	
	/**
	 * 自定义hash算法
	 * 使100000个不同字符串产生的冲突数，大概在0~3波动，使用100百万不同的字符串， 冲突数大概110+范围波动。
	 * @param string
	 * @return
	 */
	public static long hash(String string) {
		long result = 0;
		for (int i = 0; i < string.length(); i++) {
			result = seed * result + (long) string.charAt(i);
		}
		return result % Long.MAX_VALUE;
		/*
		((0 + C0) * 31 + C1) * 31 + C2
		化简得：
		C0 * 31^2 + C1 * 31^1 + C2 * 31^0
		 */
	}
}
